package com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.algorithms.shortestpath;

import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Edge;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Graph;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Vertex;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.line.IndexPriorityQueue;
import lombok.Setter;
import lombok.experimental.Accessors;

import java.util.*;

/**
 * <h1>最短路径-针对有向无环图（DAG）的快速算法<h1/>
 * <p>
 *     适用于有向无环图。
 * </p>
 * <p>
 *     核心思路是：首先基于起点构建拓扑排序。按照拓扑排序的顺序进行{@code relax  }操作
 * </p>
 */
public class FastDAGSP<T> {
    @Setter
    @Accessors(chain = true)
    private Graph<T> graph;
    //链接定点的边
    private Map<Vertex<T>, Edge<T>> map;
    //到边的最近的权重
    private Map<Vertex<T>, Double> distTo;
    private Vertex<T> source;

    private Set<Vertex<T>> marked = new HashSet<>();
    /**
     * 拓扑排序顺序
     */
    private Deque<Vertex<T>> topological = new LinkedList<>();




    public double distTo(T target) {
        return distTo.get(Vertex.create(target));
    }

    public boolean hasPathTo(T target){
        return this.map.containsKey(Vertex.create(target));
    }

    public Iterable<Edge<T>> pathTo(T target){
        //路径

        Deque<Edge<T>> result = new LinkedList<>();

        for (Edge<T> edge = this.map.get(Vertex.create(target));edge!=null;edge=map.get(edge.getFrom())) {
            result.push(edge);
        }

        return result;
    }








    private FastDAGSP<T> init(){
        //初始化 设置所有的定点权重都是无穷

        //进行基于source的拓扑排序

        dfs(source);
        this.graph.getVertices().entrySet().forEach(entity->{
            distTo.put(entity.getValue(), Double.MAX_VALUE);
        });
        //从起点开始
        distTo.put(source, 0.0d);
        //按照拓扑排序的顺序进行relax操作
        topological.forEach(tVertex -> {
            relax(tVertex);
        });


        return this;
    }


    /**
     * 进行最短路径的relax方法。判断当前边是不是目标顶点的最短路径。
     * @param vertex
     */
    private void relax(Vertex<T> vertex){
        //遍历顶点
        vertex.getNext().forEach(edge->{
            Vertex<T> to = edge.getTo();
            //判断经过当前边的权重是不是比之前的要短。
            if(distTo.get(to)>distTo.get(vertex)+edge.getWeight()){
                distTo.put(to, distTo.get(vertex)+edge.getWeight());
                this.map.put(to, edge);
            }

        });

    }


    /**
     * 递归
     * @param vertex
     */
    private void dfs(Vertex<T> vertex){
        marked.add(vertex);
        vertex.getNext().stream().map(Edge::getTo).filter(v->!marked.contains(v)).forEach(this::dfs);
        topological.push(vertex);

    }



    private FastDAGSP(Graph<T> graph, T source){
        if(!graph.isDag()){
            throw new IllegalArgumentException("功能只适配于有向无环图");
        }
        this.graph = graph;
        this.source = graph.getVertices().get(Vertex.create(source));
        this.map = new HashMap<>(graph.getVertices().keySet().size());
        this.distTo = new HashMap<>(graph.getVertices().keySet().size());

    }

    public static <T> FastDAGSP<T> create(Graph<T> graph, T source){
        return new FastDAGSP<>(graph,source).init();
    }

}
